
/**
 * 
 * 内存资源分配
 * 
 * 题目描述

有一个简易内存池，内存按照大小粒度分类，每个粒度有若干个可用内存资源，用户会进行一系列内存申请，需要按需分配内存池中的资源返回申请结果成功失败列表。

分配规则如下：

分配的内存要大于等于内存的申请量，存在满足需求的内存就必须分配，优先分配粒度小的，但内存不能拆分使用；
需要按申请顺序分配，先申请的先分配。
有可用内存分配则申请结果为true，没有可用则返回false。
注意：不考虑内存释放

输入描述
输入为两行字符串：

第一行为内存池资源列表，包含内存粒度数据信息，粒度数据间用逗号分割，一个粒度信息内用冒号分割，冒号前为内存粒度大小，冒号后为数量

资源列表不大于1024
每个粒度的数量不大于4096
第二行为申请列表，申请的内存大小间用逗号分割

申请列表不大于100000
如

64:2,128:1,32:4,1:128
50,36,64,128,127
输出描述
输出为内存池分配结果

如：

true,true,true,false,false
用例
输入	64:2,128:1,32:4,1:128
50,36,64,128,127
输出	true,true,true,false,false
说明	内存池资源包含：64K共2个、128K共1个、32K共4个、1K共128个的内存资源；
针对50,36,64,128,127的内存申请序列，分配的内存依次是：64,64,128,NULL,NULL,
第三次申请内存时已经将128分配出去，因此输出结果是：
true,true,true,false,false
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.StringJoiner;

/**
  * 

  题目解析
本题数量级稍大，暴力可能会超时。

因此我们可以：

先将内存资源列表，按照内存粒度大小，进行升序
遍历申请列表
在有序的内存资源列表中，二分查找要申请的内存大小（找到大于等于要申请的内存大小即可）
如果可以找到，则打印true，并且对应内存资源数量减1，如果内存资源数量变为0，则删除对应内存资源
如果找不到，则打印false

  */

public class 内存资源分配 {
    
    public static void main(String[] args) {
    
        try{


            Scanner scanner = new Scanner(System.in);

            //第一行 内存信息
            String[] line1Arr = Arrays.stream(scanner.nextLine().split(",")).toArray(String[]::new);

            //解析内存
            List<MenInfo> menInfosList = new ArrayList<>(line1Arr.length);

            for(String menInfoStr : line1Arr){

                int[] subArr = Arrays.stream(menInfoStr.split(":")).mapToInt(Integer::parseInt).toArray();
                //根据冒号拆分
                MenInfo subMen = new MenInfo(subArr[0], subArr[1]);
                menInfosList.add(subMen);
            }

            menInfosList.stream().map(s -> s.menSize+" == "+s.menCount).forEach(System.out::println);

            //第二行
            int[] mallocMenArr = Arrays.stream(scanner.nextLine().split(",")).filter(s -> !s.isEmpty()).mapToInt(Integer::parseInt).toArray();

            //按内存颗粒大小升序排列
            //menInfosList.sort((a, b) -> a.menSize - b.menSize);
            Collections.sort(menInfosList, (a, b) -> a.menSize - b.menSize);

            menInfosList.stream().map(s -> s.menSize+" - "+s.menCount).forEach(System.out::println);
            Arrays.stream(mallocMenArr).forEach(System.out::println);

            //分配内存

            StringJoiner stringJoiner = new StringJoiner(",");

            for(int mallocMen : mallocMenArr){

                //二分查找，找到大于等于需要分配的内存资源

                int result = doSearch(mallocMen, menInfosList);

                System.out.println("二分查找结果="+result);
                if(result < menInfosList.size()){

                    stringJoiner.add(""+true);

                    //找到一个对应下标的内存块，count 减 1 当 count == 0 删除对应的内存数据

                    if(--menInfosList.get(result).menCount == 0){

                        menInfosList.remove(result);
                    }

                } else{

                    //未找到
                    stringJoiner.add(""+false);

                }


            }


            System.out.println(stringJoiner.toString());


        }catch(Exception e){

            e.printStackTrace();
        }

    }

    private static int doSearch(int mallocMen, List<MenInfo> menInfos){

        //二分法
        int leftPosition = 0;
        int rightPosition = menInfos.size() - 1;

        while (leftPosition <= rightPosition) {
            
            int middle = (leftPosition + rightPosition) / 2;
            int middleMenSize = menInfos.get(middle).menSize;

            if(middleMenSize > mallocMen){

                //只要在左边小值区域查找
                rightPosition = middle -1;
 
            } else if(middleMenSize < mallocMen){

                //只要在右边大值区域查找
                leftPosition = middle + 1;
            } else{

                //找到对应值的下标
                return middle;
            }

        }

        return leftPosition;
    }

    private static class MenInfo {


        int menSize = 0;
        int menCount = 0;

        public MenInfo(int menSize, int menCount){

            this.menSize = menSize;
            this.menCount = menCount;
        }
    }
}
